package 我的Java学习_算法基础.day_03;

import java.util.Arrays;

public class 归并排序_非递归 {
    public static void main(String[] args) {
        int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

        mergeSort(a);

        System.out.println(Arrays.toString(a));
    }

    /**
     * 归并排序
     *
     * @param a 待排序数组
     */
    public static void mergeSort(int[] a) {

        //先求出数组的长度
        int len = a.length;
        //子数组大小分别为1、2、4、8···，刚开始是1然后2（自底向上，即先按照一个数组两个个元素排序然后四个）
        //i为1时是两个元素一个数组，2时四个元素一个数组，进行排序
        for (int i = 1; i < len; i += i) {
            //left为0从最左端开始
            int left = 0;
            //mid和right是固定的
            int mid = left + i - 1;
            int right = mid + i;
            //进行合并，将数组两两有序合并
            while (right < len) {
                //merge方法和递归用的一样
                merge(a, left, mid, right);
                //移到下一组继续合并
                left = right + 1;
                mid = left + i - 1;
                right = mid + i;
            }
            //由于并不是所有的数组大小都刚好一样大，最后一组不一定满了，所以对最后一组再来合并
            if (left < len && mid < len) {
                merge(a, left, mid, len - 1);
            }
        }

        /*
        //对上面的进行优化
        //这一个循环没有变化
        for (int i = 1; i < len; i += i) {

            //这个循环替换了上面的一大串代码
            //left为0也从最左边开始
            //left < len - 1就是循环终止条件，写出过程推断一下不难发现
            //left += (i + i)就是跳到下一个数组继续合并数组去（不难发现，数组的跨度大小总是当前i的两倍）
            for (int left = 0; left < len - i; left += (i + i)) {
                //left + i - 1代表mid
                //Math.min(left + i -1 + i, len - 1)代表合并数组的右端right，因为最后一个可能没填满，所以通过min找到最右端即可
                merge(a, left, left + i - 1, Math.min(left + i + i - 1, len - 1));
            }
        }
        */
    }

    /**
     * 将左右两边有序子数组合并
     *
     * @param a     待排序数组
     * @param left  指向第一个索引
     * @param mid   指向中间的索引
     * @param right 指向最后一个索引
     */
    public static void merge(int[] a, int left, int mid, int right) {
        int[] arr = new int[right - left + 1];
        int l = left;
        int r = mid + 1;
        int k = 0;

        while (l <= mid && r <= right) {
            if (a[l] < a[r]) {
                arr[k++] = a[l++];
            } else {
                arr[k++] = a[r++];
            }
        }
        while (l <= mid) {
            arr[k++] = a[l++];
        }
        while (r <= right) {
            arr[k++] = a[r++];
        }

        k = 0;
        while (k < arr.length) {
            a[left++] = arr[k++];
        }
    }
}
